//
// Created by 啊汤哥 on 2025/6/28.
//
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义队列节点结构
typedef struct QueueNode {
    TreeNode *data;
    struct QueueNode *next;
} QueueNode;

// 定义循环队列结构
typedef struct {
    QueueNode *front;
    QueueNode *rear;
    int size;
    int capacity;  // 表示队列最大的元素的存储数量
} Queue;

// 初始化队列
Queue* initQueue(int capacity) {
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    queue->size = 0;
    queue->capacity = capacity;
    return queue;
}

// 队列是否为空
int isEmpty(Queue *queue) {
    return queue->size == 0;
}

// 队列是否已满
int isFull(Queue *queue) {
    return queue->size == queue->capacity;
}

// 入队
void enqueue(Queue *queue, TreeNode *data) {
    if (isFull(queue)) {
        return;
    }
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    node->data = data;
    node->next = NULL;
    if (isEmpty(queue)) {
        queue->front = queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->size++;
}

// 出队
TreeNode* dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        return NULL;
    }
    QueueNode *node = queue->front;
    TreeNode *data = node->data;
    queue->front = node->next;
    free(node);
    queue->size--;
    if (isEmpty(queue)) {
        queue->rear = NULL;
    }
    return data;
}

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}

// 层次遍历
void levelOrderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    Queue *queue = initQueue(100); // 假设队列容量为100
    enqueue(queue, root);
    while (!isEmpty(queue)) {
        TreeNode *node = dequeue(queue);
        printf("%d ", node->value);
        if (node->left != NULL) {
            enqueue(queue, node->left);
        }
        if (node->right != NULL) {
            enqueue(queue, node->right);
        }
    }
    free(queue);
}

// 主函数
int main() {
    // 构建二叉树
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 层次遍历
    levelOrderTraversal(root); // 输出: 1 2 3 4 5

    return 0;
}
